k, m, n = 0, 0, 0
a, b, x, y = [], [], [], [] # b[i]保存第i种鸡买了多少只

# 递归求解：m 元买 n 只鸡问题
def buy(i: int, t: int, u: int):
    global k, m, n, a, b, x, y

    if i == k - 1:
        b[i] = (m - u) // x[i]
        if u + b[i] * x[i] == m and t + b[i] * y[i] == n:
            print('解:',
                ' '.join('%s %d只' % (a[j], b[j] * y[j]) for j in range(0, k)))
        return
    
    # 方案搜索：买 1 单位，2 单位，3单位……
    for s in range(0, n):
        b[i] = s
        if u + s * x[i] > m or t + s * y[i] > n:
            break # 当总只数或者总价钱超额时停止搜索
        # 递归搜索下一种鸡的购买方案
        buy(i + 1, t + s * y[i], u + s * x[i]);

# main
k, m, n = 3, 100, 100
a = [ "公鸡", "母鸡", "小鸡" ]
x = [ 5, 3, 1 ]
y = [ 1, 1, 3 ]
b = [0] * k
buy(0, 0, 0)
